import java.util.*;

class Solution {
    // 一般解法：
    public static List<Integer> findAnagrams2(String s, String p) {
        // 现将字符串p中的字符插入哈希表中
        int[] hashP = new int[26];
        int len = p.length()-1;
        for (int i = 0; i <= len; i++) {
            char x = p.charAt(i);
            hashP[x-'a']++;
        }
        // 遍历字符串s判断其中的元素是否满足异位词
        int[] hashS = new int[26];
        int left = 0;
        int right = len;
        List<Integer> list = new ArrayList<>();
        int count = 0;
        while (right < s.length()) {
            // 将[left,right]之间字符全部插入到哈希表中
            if (count == 0) { // 只需做一次
                for (int i = left; i <= right; i++) {
                    char x = s.charAt(i);
                    hashS[x-'a']++;
                }
                count++;
            }
            // 再遍历[left,right]之间的字符，再两个哈希表中对比查找
            boolean flag = false;
            for (int i = left; i <= right; i++) {
                char x = s.charAt(i);
                int a = hashS[x-'a'];
                int b = hashP[x-'a'];
                if (a != b) {
                    flag = true;
                    break;
                }
            }
            // 判断结果
            if (!flag) {
                list.add(left);
            }
            // 将left位置的字符从哈希表中删除
            char x = s.charAt(left++);
            hashS[x-'a']--; // 这里不能置为0
            // 将right下一个位置的字符插入哈希表
            if (right == s.length()-1) {
                break;
            }
            x = s.charAt(++right);
            hashS[x-'a']++;
        }
        return list;
    }

    // 优化后的版本：
    public static List<Integer> findAnagrams(String s, String p) {
        // 将p字符串的元素插入哈希表
        int[] hashP = new int[26];
        int len = p.length();
        for (int i = 0; i < len; i++) {
            char x = p.charAt(i);
            hashP[x-'a']++;
        }
        // 遍历s字符串寻找字母异位词
        int count = 0;
        int left = 0;
        int right = 0; // 注意：因为需要统计有效字符的个数，因此得从头开始
        List<Integer> list = new ArrayList<>();
        int[] hashS = new int[26];
        while (right < s.length()) {
            // 1、判断是否为有效字符
            char x = s.charAt(right);
            if (hashS[x-'a'] < hashP[x-'a']) { // 有效字符
                count++;
            }
            hashS[x-'a']++;
            // 2、判断窗口大小是否符合要求
            if (right-left+1 > len) {
                // 这里窗口大小一定得符合要求，
                // 因此不会出现right 超出很多的情况，因此不需要用到while循环
                // 先得判断left是否是有效字符
                char i = s.charAt(left);
                if (hashS[i-'a'] <= hashP[i-'a']) {
                    count--;
                }
                hashS[i-'a']--;
                left++;
            }
            // 3、这里窗口大小一定是符合要求的，因此可以判断是否为字母异位词
            if (count == len) {
                list.add(left);
            }
            right++;
        }
        return list;
    }


    public static void main(String[] args) {
        String s =  "cbaebabacd";
        String p = "abc";
        List<Integer> list = findAnagrams(s, p);
        System.out.println(list);
    }
}